#include <iostream>

template <typename T>
struct Queue {
private:
	struct Node {
		T data;
		Node* next;
		Node(const T& x) {
			data = x;
			next = NULL;
		}
	};

private:
	Node* head;
	Node* tail;

public:
	Queue() {
		head = NULL;
		tail = NULL;
	}

	~Queue() {
		while (!Empty()) {
			Remove();
		}
	}

	bool Empty() {
		return head == NULL;
	}

	Queue& Add(const T& x) {
		Node* p = new Node(x);
		if (Empty()) {
			head = p;
		}
		else {
			tail->next = p;
		}
		tail = p;
		return *this;


	}


	T Remove() {
		if (Empty()) {
			throw "queue is empty";
		}

		Node* p = head;
		head = head->next;

		if (head == NULL) {
			tail = NULL;
		}

		T x = p->data;
		delete p;
		return x;
	}

	void Print() {
		Node* p = head;
		while (p != NULL) {
			std::cout << p->data << " ";
			p = p->next;
		}
	}

};

/**
 * 链表实现的队列
 */
int main() {

	Queue<int> q;

	q.Add(3).Add(5).Add(1).Print();

	std::cout << "\n";

	q.Remove();

	q.Print();

	std::cout << "\n";

	q.Add(777).Add(888).Print();


	return 0;
}
